package com.labuladong.sort;

import java.util.Arrays;

public class CountingSort {

    // 计数排序方法
    public static int[] sort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums; // 如果输入为空或长度为0，则直接返回
        }

        // 找到最大和最小元素
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        // 根据最大值和最小值，将元素映射到从 0 开始的索引值
        final int offset = -min;
        int[] count = new int[max - min + 1];

        // 统计每个元素出现的次数
        for (int num : nums) {
            count[num + offset]++;
        }

        // 累加 count 数组，得到的是 nums[i] 在排序后的数组中的结束位置
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 根据每个元素排序后的索引位置，完成排序
        // 这里注意，我们从后往前遍历 nums，是为了保证排序的稳定性
        int[] sorted = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = nums[i] + offset;
            sorted[count[index] - 1] = nums[i];
            count[index]--;
        }
        return sorted;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 2, 0, 2, -3, -1, 3, 0};
        int[] result = sort(nums);
        System.out.println(Arrays.toString(result));
    }
}